package org.totoro.structure.tree.heap;

import org.totoro.structure.list.List;
import org.totoro.structure.list.impl.ArrayList;

import java.util.Objects;

/**
 * @author daocr
 * @date 2020/4/3
 */
public class ArrayMaxHeap<E extends Comparable<E>> {

    private List<E> list;

    private int size;

    public ArrayMaxHeap() {
        list = new ArrayList<>();
    }

    /**
     * 判断是否为 空
     *
     * @return
     */
    public boolean isEmpty() {
        return list.size() == 0;
    }

    /**
     * 获取  size
     *
     * @return
     */
    public int size() {
        return list.size();
    }


    /**
     * 下标起始位置为0
     *
     * @param index
     * @return
     */
    private int parentIndex(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("下标 0 ，没有父节点");
        }
        return (index - 1) / 2;
    }

    /**
     * 下标起始位置为0
     *
     * @param index
     * @return
     */
    private int leftIndex(int index) {
        return index + 2 + 1;
    }

    /**
     * 下标起始位置为0
     *
     * @param index
     * @return
     */
    private int rightIndex(int index) {
        return index + 2 + 2;
    }


    public void add(E element) {
        list.addLast(element);

        siftUp(list.size() - 1);
    }

    /**
     * 上浮操作
     *
     * @param index
     */
    private void siftUp(int index) {
        /**
         * 判断自己是否比父节点大
         */
        while (list.get(index).compareTo(list.get(parentIndex(index))) > 0) {
            int parentIndex = parentIndex(index);
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    /**
     * 下沉
     *
     * @param index
     */
    private void siftDown(int index) {

        //最后一个元素
        int lastIndex = size() - 1;
        E last = list.get(lastIndex);

        //把最后一个元素设置为null
        list.add(lastIndex, null);

        siftDown(index, leftIndex(index), rightIndex(index));

    }

    private void siftDown(int index, int leftIndex, int rightIndex) {

        //当前节点
        E curValue = list.get(index);
        //当前节点 左孩子节点
        E leftValue = list.get(leftIndex);
        //当前节点 右孩子节点
        E rightValue = list.get(rightIndex);

        // 当前节点小于左孩子
        if (Objects.nonNull(leftValue) && curValue.compareTo(leftValue) < 0) {

        }
        //当前节点小于小于右孩子节点


    }

    /**
     * 交换节点的值
     *
     * @param index
     * @param parentIndex
     * @return
     */
    private void swap(int index, int parentIndex) {
        E e = list.get(index);
        list.add(index, list.get(parentIndex));
        list.add(parentIndex, e);
    }


}
